package no40;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/15 11:11
 * 最小的 k 个数
 * https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/
 */
public class Solution {

    // 大根堆的思路
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k]; // 用于存储结果
        // 用于构建大根堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        // 先将前 k 个数存入小根堆
        int index = 0;
        while (k-- != 0) {
            maxHeap.offer(arr[index++]);
        }
        // 继续比较剩余的数字, 如果比堆顶还要小, 则出堆顶, 并加入该元素
        // 在大根堆中始终维护 k 个数字
        while (index < arr.length) {
            if (!maxHeap.isEmpty() && maxHeap.peek() > arr[index]) {
                maxHeap.poll();
                maxHeap.offer(arr[index]);
            }
            index++;
        }
        // 将结果保存并返回
        for (int i = 0; i < res.length; i++) {
            res[i] = maxHeap.poll();
        }
        return res;
    }
}
